package gold.digger;

/**
 * Created by fanzhenyu02 on 2020/3/1.
 */
public class LC494 {

    /**
     * 由于dp数组元素对称，还可以考虑未来进一步优化
     */
    public int findTargetSumWays(int[] arr, int S) {
        int sum = 0;
        for (int i = 0; i < arr.length; i++) {
            sum += arr[i];
        }
        if (sum < Math.abs(S)) {
            return 0;
        }

        int[] dpPre = new int[2 * sum + 2];
        int[] dpAf = new int[2 * sum + 2];
        boolean isAf = true;
        for (int i = 0 - sum; i <= sum; i++) {
            dpPre[i + sum] = arr[0] == Math.abs(i) ? 1 : 0;
            if (arr[0] == 0 && i == 0) {
                dpPre[i + sum] = 2;
            }
        }

        for (int i = 1; i < arr.length; i++) {
            int[] dpCur = isAf ? dpAf : dpPre;
            int[] dpCurPre = isAf ? dpPre : dpAf;
            isAf = !isAf;
            for (int j = 0 - sum; j <= sum; j++) {
                int minus = j - arr[i] < 0 - sum ? 0 : dpCurPre[j - arr[i] + sum];
                int add = j + arr[i] > sum ? 0 : dpCurPre[j + arr[i] + sum];
                dpCur[j + sum] = minus + add;
            }
        }

        int[] dpCur = isAf ? dpPre : dpAf;
        return dpCur[S + sum];
    }

    public static void main(String[] args) {
        LC494 an = new LC494();
        int[] arr = {0, 0, 0, 0, 1};
        System.out.println(an.findTargetSumWays(arr, 1));

    }
}
